import java.util.PriorityQueue;
import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2025-07-20
 * Time: 15:03
 */
public class Test75 {
    // 方法1:利用优先级队列
//    public static int findKthLargest(int[] num, int k) {
//        PriorityQueue<Integer> q = new PriorityQueue<>();
//        for(int i = 0; i < num.length; i++) {
//           q.offer(num[i]);
//           if(q.size() > k) {
//               q.poll();
//           }
//        }
//        return q.peek();
//    }

    // 方法2：快速排序
    public static int findKthLargest(int[] num, int k) {
        return qsort(num,0,num.length-1,k);
    }

    private static int qsort(int[] num,int l, int r, int k) {
        if(l == r) {
            return num[l];
        }
        // 区间 l,r
        // // right,r    left+1,right-1,    l,left
        int key = num[new Random().nextInt(r-l+1)+l];
        int left = l-1, right = r+1, i = l;
        while(i < right) {
            if(num[i] < key) {
                swap(num,++left,i++);
            }else if(num[i] == key) {
                i++;
            }else {
                swap(num,--right,i);
            }
        }

        int a = r-right+1,b = right-left-1;
        if(a > k) {
            return qsort(num,right,r,k);
        }else if (a+b >= k) {
            return key;
        }else {
            return qsort(num,l,left,k-a-b);
        }
    }

    public static void swap(int[] num,int i,int j) {
        int tmp = num[i];
        num[i] = num[j];
        num[j] = tmp;
    }

    public static void main(String[] args) {
        int[] num = {3,2,1,5,6,4};
        int k = 2;
        int ret = findKthLargest(num,k);
        System.out.println(ret);
    }
}
